{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Sideway Jumps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSideJumps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最少侧跳次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的 <strong>3 跑道道路</strong> ，它总共包含 <code>n + 1</code> 个 <strong>点</strong> ，编号为 <code>0</code> 到 <code>n</code> 。一只青蛙从 <code>0</code> 号点第二条跑道 <strong>出发</strong> ，它想要跳到点 <code>n</code> 处。然而道路上可能有一些障碍。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n + 1</code> 的数组 <code>obstacles</code> ，其中 <code>obstacles[i]</code> （<b>取值范围从 0 到 3</b>）表示在点 <code>i</code> 处的 <code>obstacles[i]</code> 跑道上有一个障碍。如果 <code>obstacles[i] == 0</code> ，那么点 <code>i</code> 处没有障碍。任何一个点的三条跑道中 <strong>最多有一个</strong> 障碍。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，如果 <code>obstacles[2] == 1</code> ，那么说明在点 2 处跑道 1 有障碍。</li>\n",
    "</ul>\n",
    "\n",
    "<p>这只青蛙从点 <code>i</code> 跳到点 <code>i + 1</code> 且跑道不变的前提是点 <code>i + 1</code> 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 <strong>同一个</strong> 点处 <strong>侧跳</strong> 到 <strong>另外一条</strong> 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>这只青蛙从点 0 处跑道 <code>2</code> 出发，并想到达点 <code>n</code> 处的 <strong>任一跑道</strong> ，请你返回 <strong>最少侧跳次数</strong> 。</p>\n",
    "\n",
    "<p><strong>注意</strong>：点 <code>0</code> 处和点 <code>n</code> 处的任一跑道都不会有障碍。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex1.png\" style=\"width: 500px; height: 244px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>obstacles = [0,1,2,3,0]\n",
    "<b>输出：</b>2 \n",
    "<b>解释：</b>最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。\n",
    "注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex2.png\" style=\"width: 500px; height: 196px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>obstacles = [0,1,1,3,3,0]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>跑道 2 没有任何障碍，所以不需要任何侧跳。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex3.png\" style=\"width: 500px; height: 196px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>obstacles = [0,2,1,0,3,0]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>最优方案如上图所示。总共有 2 次侧跳。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>obstacles.length == n + 1</code></li>\n",
    "\t<li><code>1 <= n <= 5 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= obstacles[i] <= 3</code></li>\n",
    "\t<li><code>obstacles[0] == obstacles[n] == 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-sideway-jumps](https://leetcode.cn/problems/minimum-sideway-jumps/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-sideway-jumps](https://leetcode.cn/problems/minimum-sideway-jumps/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2,3,0]', '[0,1,1,3,3,0]', '[0,2,1,0,3,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d=[1,0,1]\n",
    "        for i in range(1,len(obstacles)):\n",
    "            minc=inf\n",
    "            for j in range(3):\n",
    "                if j==obstacles[i]-1:d[j]=inf\n",
    "                else:minc=min(minc,d[j])\n",
    "            for j in range(3):\n",
    "                if j!=obstacles[i]-1:d[j]=min(d[j],minc+1)\n",
    "        return min(d)\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        # n = len(obstacles)\n",
    "        # f = [[inf] * 3 for _ in range(n)] \n",
    "        # f[0][0] = 1\n",
    "        # f[0][2] = 1\n",
    "        # f[0][1] = 0 \n",
    "        # for i in range(1, n):\n",
    "        #     obs = obstacles[i] - 1\n",
    "        #     for j in range(3):\n",
    "        #         if j == obs:\n",
    "        #             continue\n",
    "        #         f[i][j] = f[i-1][j]\n",
    "        #         for k in range(3):\n",
    "        #             if k == obs or k == j:\n",
    "        #                 continue\n",
    "        #             f[i][j] = min(f[i][j], f[i-1][k]+1)\n",
    "        # return min(f[n-1])\n",
    "\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        jumps = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    jumps[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, jumps[j])\n",
    "            \n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    jumps[j] = min(jumps[j], minCnt + 1)\n",
    "            \n",
    "        \n",
    "        return min(jumps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, n):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "#         jumps = [1, 0, 1]\n",
    "#         for obstacle in obstacles[1:]:\n",
    "#             minCnt = inf\n",
    "#             for j in range(3):\n",
    "#                 if j == obstacle - 1:\n",
    "#                     jumps[j] = inf\n",
    "#                 else:\n",
    "#                     minCnt = min(minCnt, jumps[j])\n",
    "            \n",
    "#             for j in range(3):\n",
    "#                 if j != obstacle - 1:\n",
    "#                     jumps[j] = min(jumps[j], minCnt + 1)        \n",
    "#         return min(jumps)\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        l=0\n",
    "        loc=[1,2,3]\n",
    "        ru=[2]\n",
    "        for i in range(1,len(obstacles)):\n",
    "            if obstacles[i] in ru:\n",
    "                if (len(ru)==1):\n",
    "                    l+=1\n",
    "                    ru.extend(loc)\n",
    "                    ru.remove(obstacles[i])\n",
    "                    ru.remove(obstacles[i])\n",
    "                    if (obstacles[i-1]!=0):\n",
    "                        ru.remove(obstacles[i-1])\n",
    "                else:\n",
    "                    ru.remove(obstacles[i])\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1,0,1]\n",
    "        for i in range(1,len(obstacles)):\n",
    "            minCnt = inf \n",
    "            for j in range(3):\n",
    "                if j==obstacles[i]-1:\n",
    "                    d[j] = inf \n",
    "                else:\n",
    "                    minCnt = min(minCnt,d[j])\n",
    "            for j in range(3):\n",
    "                if j!=obstacles[i]-1:\n",
    "                    d[j] = min(d[j],minCnt+1)\n",
    "        return min(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        f = [1, 0, 1]\n",
    "        for v in obstacles[1:]:\n",
    "            for j in range(3):\n",
    "                if v == j + 1:\n",
    "                    f[j] = inf\n",
    "                    break\n",
    "            x = min(f) + 1\n",
    "            for j in range(3):\n",
    "                if v != j + 1:\n",
    "                    f[j] = min(f[j], x)\n",
    "        return min(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        dp = [1, 0, 1]\n",
    "        n = len(obstacles)-1\n",
    "        for i in range(1, n):\n",
    "            obs_idx=obstacles[i] \n",
    "            if obs_idx==0:\n",
    "                dp=[min(dp[0], dp[1]+1, dp[2]+1),min(dp[1], dp[0]+1, dp[2]+1),min(dp[2], dp[0]+1, dp[1]+1)]\n",
    "            elif obs_idx == 1:\n",
    "                dp=[inf,min(dp[1],dp[2]+1),min(dp[2],dp[1]+1)]\n",
    "            elif obs_idx==2:\n",
    "                dp=[min(dp[0], dp[2]+1),inf,min(dp[2], dp[0]+1)]\n",
    "            elif obs_idx==3:\n",
    "                dp=[min(dp[0],dp[1]+1),min(dp[1],dp[0]+1),inf]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "\n",
    "        self.max = 5 * 1e5 + 1\n",
    "        dp = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            mincnt = self.max\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    dp[j] = self.max\n",
    "                else:\n",
    "                    mincnt = min(mincnt, dp[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] -1:\n",
    "                    dp[j] = min(dp[j], mincnt+1)\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        jumps = [1, 0, 1]\n",
    "        for obstacle in obstacles[1:]:\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacle - 1:\n",
    "                    jumps[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, jumps[j])\n",
    "            \n",
    "            for j in range(3):\n",
    "                if j != obstacle - 1:\n",
    "                    jumps[j] = min(jumps[j], minCnt + 1)        \n",
    "        return min(jumps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        res = 0\n",
    "        num = 2\n",
    "        choices = {1, 2, 3}\n",
    "        for i in range(n - 1):\n",
    "            if obstacles[i+1] == num:  # 跑道侧方前面有障碍\n",
    "                choi = choices - {num, obstacles[i]}\n",
    "                if len(choi) == 1:\n",
    "                    num = choi.pop()\n",
    "                    res += 1\n",
    "                else:\n",
    "                    tmp = {}\n",
    "                    for j in choi:\n",
    "                        k = i\n",
    "                        while k < n and obstacles[k] != j:\n",
    "                            k += 1\n",
    "                        tmp[k] = j \n",
    "                    num = tmp[max(tmp)]\n",
    "                    res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d=[1,0,1]\n",
    "        for i in range(1,len(obstacles)):\n",
    "            minCnt=inf\n",
    "            for j in range(3):\n",
    "                if obstacles[i]-1==j:\n",
    "                    d[j]=inf\n",
    "                else:\n",
    "                    minCnt=min(minCnt,d[j])\n",
    "            for j in range(3):\n",
    "                if j!=obstacles[i]-1:\n",
    "                    d[j]=min(minCnt+1,d[j])\n",
    "        return min(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        dp = [1, 0, 1]\n",
    "        for o in obstacles[1:]:\n",
    "            if o:\n",
    "                dp[o - 1] = inf\n",
    "            cur = min(dp)\n",
    "            for j in range(3):\n",
    "                if j != o - 1:\n",
    "                    dp[j] = min(dp[j], cur + 1)\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "\n",
    "#         # the frog can proceed greedily if curent road ront is an obstacle\n",
    "\n",
    "#         # @cache\n",
    "#         # def dfs(idx, pos):\n",
    "\n",
    "#         #     if idx == len(obstacles) - 1:\n",
    "#         #         return 0\n",
    "            \n",
    "#         #     if obstacles[idx + 1] != pos:\n",
    "#         #         return dfs(idx + 1, pos)\n",
    "            \n",
    "#         #     ret = inf\n",
    "#         #     for i in range(1, 4):\n",
    "#         #         if i != pos and obstacles[idx] != i:\n",
    "#         #             ret = min(ret, 1 + dfs(idx, i))\n",
    "            \n",
    "#         #     return ret\n",
    "        \n",
    "#         # return dfs(0, 2)\n",
    "\n",
    "#         obstacles = [v - 1 for v in obstacles]\n",
    "\n",
    "#         n = len(obstacles)\n",
    "#         dp = [ [0 for _ in range(3)] for _ in range(n + 1)]\n",
    "#         dp[0][0] = 1\n",
    "#         dp[0][2] = 1\n",
    "\n",
    "#         for i in range(1, n):\n",
    "#             ob = obstacles[i]\n",
    "#             dp[i][ob] = inf\n",
    "\n",
    "#             for j in range(3):\n",
    "\n",
    "#                 other1 = (j + 1) % 3 if obstacles[i] != (j + 1) % 3 else j\n",
    "#                 other2 = (j + 2) % 3 if obstacles[i] != (j + 2) % 3 else j\n",
    "#                 if j != ob:\n",
    "#                     dp[i][j] = min(dp[i-1][j], dp[i-1][other1] + 1, dp[i-1][other2] + 1)\n",
    "        \n",
    "#         #print(dp)\n",
    "#         return min(dp[n - 1])\n",
    "\n",
    "#         # dfs with no cache, timeout\n",
    "#         # dfs with cache , exceed stack depth\n",
    "\n",
    "# from answer:\n",
    "# the key is calculate each point minimum in two step instead single step\n",
    "# 性能大约快50%\n",
    "# 思路更多的是不考虑前一个障碍，而是只考虑当前的障碍以及能到达的位置\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "\n",
    "#         # the frog can proceed greedily if curent road ront is an obstacle\n",
    "\n",
    "#         # @cache\n",
    "#         # def dfs(idx, pos):\n",
    "\n",
    "#         #     if idx == len(obstacles) - 1:\n",
    "#         #         return 0\n",
    "            \n",
    "#         #     if obstacles[idx + 1] != pos:\n",
    "#         #         return dfs(idx + 1, pos)\n",
    "            \n",
    "#         #     ret = inf\n",
    "#         #     for i in range(1, 4):\n",
    "#         #         if i != pos and obstacles[idx] != i:\n",
    "#         #             ret = min(ret, 1 + dfs(idx, i))\n",
    "            \n",
    "#         #     return ret\n",
    "        \n",
    "#         # return dfs(0, 2)\n",
    "\n",
    "#         obstacles = [v - 1 for v in obstacles]\n",
    "\n",
    "#         n = len(obstacles)\n",
    "#         dp = [ [0 for _ in range(3)] for _ in range(n + 1)]\n",
    "#         dp[0][0] = 1\n",
    "#         dp[0][2] = 1\n",
    "\n",
    "#         for i in range(1, n):\n",
    "#             ob = obstacles[i]\n",
    "#             dp[i][ob] = inf\n",
    "\n",
    "#             for j in range(3):\n",
    "\n",
    "#                 other1 = (j + 1) % 3 if obstacles[i] != (j + 1) % 3 else j\n",
    "#                 other2 = (j + 2) % 3 if obstacles[i] != (j + 2) % 3 else j\n",
    "#                 if j != ob:\n",
    "#                     dp[i][j] = min(dp[i-1][j], dp[i-1][other1] + 1, dp[i-1][other2] + 1)\n",
    "        \n",
    "#         #print(dp)\n",
    "#         return min(dp[n - 1])\n",
    "\n",
    "#         # dfs with no cache, timeout\n",
    "#         # dfs with cache , exceed stack depth\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        l=0\n",
    "        loc=[1,2,3]\n",
    "        ru=[2]\n",
    "        for i in range(1,len(obstacles)):\n",
    "            if obstacles[i] in ru:\n",
    "                if (len(ru)==1):\n",
    "                    l+=1\n",
    "                    ru.extend(loc)\n",
    "                    ru.remove(obstacles[i])\n",
    "                    ru.remove(obstacles[i])\n",
    "                    if (obstacles[i-1]!=0):\n",
    "                        ru.remove(obstacles[i-1])\n",
    "                else:\n",
    "                    ru.remove(obstacles[i])\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        '''\n",
    "        求的是最少侧跳次数\n",
    "        注意，侧跳可以跳到任意跑道，只要没有障碍\n",
    "        dp的思想有转移方程，但是不是一个DAG\n",
    "        如何转变？添加一个隐藏层minCnt\n",
    "\n",
    "        求到达每个点的最少侧跳次数\n",
    "        朴素bfs也无法维护，最好的方法就是贪心最小堆\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            minCnt=inf\n",
    "            if i==-1:\n",
    "                if j==2:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            if obstacles[i]==j:\n",
    "                return inf\n",
    "            for x in range(1,4):\n",
    "                if x!=j and obstacles[i]!=x:\n",
    "                    minCnt=min(minCnt,dfs(i-1,x)+1)\n",
    "            minCnt=min(minCnt,dfs(i-1,j))\n",
    "            return minCnt\n",
    "        n=len(obstacles)\n",
    "        \n",
    "        ans=min(dfs(n-1,1),dfs(n-1,2),dfs(n-1,3))\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "        '''\n",
    "\n",
    "        n=len(obstacles)\n",
    "        f=[inf,1,0,1]\n",
    "        for i in range(n):\n",
    "            minCnt=inf\n",
    "            for j in range(1,4):\n",
    "                if obstacles[i]==j:\n",
    "                    f[j]=inf\n",
    "                    continue\n",
    "                for x in range(1,4):\n",
    "                    if x!=j and obstacles[i]!=x:\n",
    "                        minCnt=min(minCnt,f[x]+1)\n",
    "                f[j]=min(f[j],minCnt)\n",
    "        return min(f)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        arr = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            if obstacles[i]:\n",
    "                arr[obstacles[i] - 1] = float('inf')\n",
    "            lastmin = min(arr)\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    arr[j] = min(arr[j], lastmin + 1)\n",
    "        return min(arr)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles) - 1\n",
    "        dp = [float('inf')]*3\n",
    "        # dp[i][j]表示到达点i的跑道j的最少侧跳次数\n",
    "        dp[1] = 0\n",
    "        dp[0],dp[2] = 1,1\n",
    "        for i in range(1,n+1):\n",
    "            tmp = dp[:]\n",
    "            dp = [float('inf')]*3\n",
    "            cur_min = float('inf')\n",
    "            for j in range(3):\n",
    "                if j!=obstacles[i]-1:\n",
    "                    if obstacles[i-1]-1!=j:\n",
    "                        dp[j] = tmp[j]\n",
    "                        cur_min = min(cur_min, dp[j])\n",
    "            for j in range(3):\n",
    "                if j!=obstacles[i]-1:\n",
    "                    dp[j] = min(dp[j], cur_min + 1)\n",
    "            pass\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        d = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    d[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, d[j])\n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    d[j] = min(d[j], minCnt + 1)\n",
    "        return min(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        jumps = [1, 0, 1]\n",
    "        for obstacle in obstacles[1:]:\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacle - 1:\n",
    "                    jumps[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, jumps[j])\n",
    "            \n",
    "            for j in range(3):\n",
    "                if j != obstacle - 1:\n",
    "                    jumps[j] = min(jumps[j], minCnt + 1)        \n",
    "        return min(jumps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        jumps = [1, 0, 1]\n",
    "        for i in range(1, len(obstacles)):\n",
    "            minCnt = inf\n",
    "            for j in range(3):\n",
    "                if j == obstacles[i] - 1:\n",
    "                    jumps[j] = inf\n",
    "                else:\n",
    "                    minCnt = min(minCnt, jumps[j])\n",
    "            \n",
    "            for j in range(3):\n",
    "                if j != obstacles[i] - 1:\n",
    "                    jumps[j] = min(jumps[j], minCnt + 1)\n",
    "            \n",
    "        \n",
    "        return min(jumps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        f = [1, 0, 1]\n",
    "        for v in obstacles[1:]:\n",
    "            for j in range(3):\n",
    "                if v == j + 1:\n",
    "                    f[j] = inf\n",
    "                    break\n",
    "            x = min(f) + 1\n",
    "            for j in range(3):\n",
    "                if v != j + 1:\n",
    "                    f[j] = min(f[j], x)\n",
    "        return min(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        #青蛙跳到第i个位置，在第j个跑道的最小次数，如果跳不到则返回-1\n",
    "        n = len(obstacles) - 1\n",
    "        dp = [[0]*3] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            for j in range(3):\n",
    "                if i == 0:\n",
    "                    if j != 1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = 0\n",
    "                if obstacles[i] == 0:\n",
    "                    if obstacles[i-1] - 1 != j:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]) + 1\n",
    "                else:\n",
    "                    if obstacles[i] == j + 1:\n",
    "                        dp[i][j] = -1\n",
    "                    else:\n",
    "                        li=[0, 1, 2]\n",
    "                        li.remove(j)\n",
    "                        li.remove(obstacles[i]-1)\n",
    "                        ind = li[0]\n",
    "                        if dp[i-1][j] == -1:\n",
    "                            dp[i][j] = 1 + dp[i-1][ind]\n",
    "                        else:\n",
    "                            dp[i][j] = dp[i-1][j]\n",
    "        ansl = []\n",
    "        for j in range(3):\n",
    "            if dp[n][j] >= 0:\n",
    "                ansl.append(dp[n][j])\n",
    "        return min(ansl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        dp1, dp2, dp3 = 1, 0, 1\n",
    "        for i in range(1, len(obstacles)):\n",
    "            if obstacles[i] == 1:\n",
    "                dp1 = inf\n",
    "                dp2 = min(dp2, dp1 + 1, dp3 + 1)\n",
    "                dp3 = min(dp3, dp1 + 1, dp2 + 1)\n",
    "            elif obstacles[i] == 2:\n",
    "                dp2 = inf\n",
    "                dp1 = min(dp1, dp2 + 1, dp3 + 1)\n",
    "                dp3 = min(dp3, dp1 + 1, dp2 + 1)\n",
    "            elif obstacles[i] == 3:\n",
    "                dp3 = inf\n",
    "                dp1 = min(dp1, dp2 + 1, dp3 + 1)\n",
    "                dp2 = min(dp2, dp1 + 1, dp3 + 1)\n",
    "            else:\n",
    "                dp1 = min(dp1, dp2 + 1, dp3 + 1)\n",
    "                dp2 = min(dp2, dp1 + 1, dp3 + 1)\n",
    "                dp3 = min(dp3, dp1 + 1, dp2 + 1)\n",
    "            #print(f\"{i} {dp1} {dp2} {dp3}\")\n",
    "        return min(dp1, dp2, dp3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        dp = [float('inf')]*3 \n",
    "\n",
    "        if obstacles[0] != 1: dp[0] = 1\n",
    "        dp[1] = 0\n",
    "        if obstacles[0] != 3: dp[2] = 1\n",
    "\n",
    "        for idx in range(1, n):\n",
    "            tmp = [float('inf')]*3 \n",
    "            for i in range(3):\n",
    "                j, k = (i+1)%3, (i+2)%3\n",
    "                if obstacles[idx] != i+1: \n",
    "                    if obstacles[idx] != j+1: tmp[i] = min([tmp[i], dp[i], dp[j]+1])\n",
    "                    if obstacles[idx] != k+1: tmp[i] = min([tmp[i], dp[i], dp[k]+1])\n",
    "\n",
    "            dp = tmp[:]\n",
    "                \n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        dp = [1, 0, 1]\n",
    "        for i in range(n):\n",
    "            x = obstacles[i]\n",
    "            if x:\n",
    "                dp[x - 1] = inf\n",
    "            low = min(dp)\n",
    "            for j in range(3):\n",
    "                if j != x - 1:\n",
    "                    dp[j] = dp[j] if dp[j] < low + 1 else low + 1\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        pre = [1, 0, 1]\n",
    "        for i in range(n):\n",
    "            x = obstacles[i]\n",
    "            if x:\n",
    "                pre[x-1] = inf\n",
    "                \n",
    "            cur = [inf, inf, inf]\n",
    "            for j in range(3):\n",
    "                if j != x-1:\n",
    "                    cur[j] = min(pre[j], min(pre) + 1)\n",
    "            pre = cur[:]\n",
    "        return min(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        obs = [list() for _ in range(3)]\n",
    "        for i in range(n):\n",
    "            if obstacles[i] != 0:\n",
    "                obs[obstacles[i] - 1].append(i)\n",
    "        cur = 1\n",
    "        idx = [0] * 3\n",
    "        ans = 0\n",
    "        while idx[cur] < len(obs[cur]):\n",
    "            i = obs[cur][idx[cur]] - 1\n",
    "            for j in range(3):\n",
    "                while idx[j] < len(obs[j]) and obs[j][idx[j]] < i:\n",
    "                    idx[j] += 1\n",
    "                if idx[j] >= len(obs[j]):\n",
    "                    cur = j\n",
    "                    break\n",
    "                elif obs[j][idx[j]] > obs[cur][idx[cur]]:\n",
    "                    cur = j\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        dp = [[0]*n for _ in range(3)]\n",
    "        dp[0][0] = 1\n",
    "        dp[2][0] = 1\n",
    "        for i in range(1, n):\n",
    "            if obstacles[i] == 0:\n",
    "                dp[0][i] = min(dp[0][i-1], dp[1][i-1]+1, dp[2][i-1]+1)\n",
    "                dp[1][i] = min(dp[1][i-1], dp[0][i-1]+1, dp[2][i-1]+1)\n",
    "                dp[2][i] = min(dp[2][i-1], dp[0][i-1]+1, dp[1][i-1]+1)\n",
    "            elif obstacles[i] == 1:\n",
    "                dp[0][i] = float('inf')\n",
    "                dp[1][i] = min(dp[1][i-1], dp[2][i-1]+1)\n",
    "                dp[2][i] = min(dp[2][i-1], dp[1][i-1]+1)\n",
    "            elif obstacles[i] == 2:\n",
    "                dp[0][i] = min(dp[0][i-1], dp[2][i-1]+1)\n",
    "                dp[1][i] = float('inf')\n",
    "                dp[2][i] = min(dp[2][i-1], dp[0][i-1]+1)\n",
    "            elif obstacles[i] == 3:\n",
    "                dp[0][i] = min(dp[0][i-1], dp[1][i-1]+1)\n",
    "                dp[1][i] = min(dp[1][i-1], dp[0][i-1]+1)\n",
    "                dp[2][i] = float('inf')\n",
    "        return min(dp[0][-1], dp[1][-1], dp[2][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        dp = []\n",
    "        for i in range(3):\n",
    "            dp.append([0] * n)\n",
    "        dp[0][0] = 1\n",
    "        dp[2][0] = 1\n",
    "        for i in range(1,n):\n",
    "            for j in range(3):\n",
    "                if obstacles[i] == j + 1:\n",
    "                    dp[j][i] = n + 1\n",
    "                else:\n",
    "                    dp[j][i] = dp[j][i-1]\n",
    "            for j in range(3):\n",
    "                if obstacles[i] != j + 1:\n",
    "                    dp[j][i] = min(dp[j][i],dp[(j+1)%3][i]+1)\n",
    "                    dp[j][i] = min(dp[j][i],dp[(j+2)%3][i]+1)\n",
    "        # print(\"dp \",dp)\n",
    "        return min(dp[0][n-1],min(dp[1][n-1],dp[2][n-1]))               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        N = len(obstacles)\n",
    "        dp = [ [ inf ] * 4 for _ in range(N) ]\n",
    "        dp[0][1] = 1\n",
    "        dp[0][2] = 0\n",
    "        dp[0][3] = 1\n",
    "        for i, a in enumerate(obstacles):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            for x in range(1, 4):\n",
    "                dp[i][x] = dp[i-1][x] if x != obstacles[i] else inf\n",
    "            if obstacles[i] != 1:\n",
    "                dp[i][1] = min(dp[i][1], dp[i][2] + 1, dp[i][3] + 1)\n",
    "            if obstacles[i] != 2:\n",
    "                dp[i][2] = min(dp[i][2], dp[i][1] + 1, dp[i][3] + 1)\n",
    "            if obstacles[i] != 3:\n",
    "                dp[i][3] = min(dp[i][3], dp[i][1] + 1, dp[i][2] + 1)\n",
    "\n",
    "        # print(dp)\n",
    "        return min(dp[-1][1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "\n",
    "        # the frog can proceed greedily if curent road ront is an obstacle\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(idx, pos):\n",
    "\n",
    "        #     if idx == len(obstacles) - 1:\n",
    "        #         return 0\n",
    "            \n",
    "        #     if obstacles[idx + 1] != pos:\n",
    "        #         return dfs(idx + 1, pos)\n",
    "            \n",
    "        #     ret = inf\n",
    "        #     for i in range(1, 4):\n",
    "        #         if i != pos and obstacles[idx] != i:\n",
    "        #             ret = min(ret, 1 + dfs(idx, i))\n",
    "            \n",
    "        #     return ret\n",
    "        \n",
    "        # return dfs(0, 2)\n",
    "\n",
    "        obstacles = [v - 1 for v in obstacles]\n",
    "\n",
    "        n = len(obstacles)\n",
    "        dp = [ [0 for _ in range(3)] for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        dp[0][2] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            ob = obstacles[i]\n",
    "            dp[i][ob] = inf\n",
    "\n",
    "            for j in range(3):\n",
    "\n",
    "                other1 = (j + 1) % 3 if obstacles[i] != (j + 1) % 3 else j\n",
    "                other2 = (j + 2) % 3 if obstacles[i] != (j + 2) % 3 else j\n",
    "                if j != ob:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i-1][other1] + 1, dp[i-1][other2] + 1)\n",
    "        \n",
    "        #print(dp)\n",
    "        return min(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n=len(obstacles)\n",
    "        dp=[[-1,-1,-1] for _ in range(n)]\n",
    "        if(obstacles[0]==2):\n",
    "            dp[0][1]=1\n",
    "        else :\n",
    "            dp[0][1]=0\n",
    "        if(obstacles[0]!=1):\n",
    "            dp[0][0]=1\n",
    "        if(obstacles[0]!=3):\n",
    "            dp[0][2]=1\n",
    "        for i in  range(1,n):\n",
    "            if(obstacles[i]==0):\n",
    "                if dp[i-1][0]!=-1:\n",
    "                    dp[i][0]=dp[i-1][0]\n",
    "                else:\n",
    "                    dp[i][1]=dp[i-1][1]\n",
    "                    dp[i][2]=dp[i-1][2]\n",
    "                    dp[i][0]=min(dp[i-1][1],dp[i-1][2])+1\n",
    "                    continue\n",
    "                if dp[i-1][1]!=-1:\n",
    "                    dp[i][1]=dp[i-1][1]\n",
    "                else:\n",
    "                    dp[i][0]=dp[i-1][0]\n",
    "                    dp[i][2]=dp[i-1][2]\n",
    "                    dp[i][1]=min(dp[i-1][0],dp[i-1][2])+1\n",
    "                    continue\n",
    "                if dp[i-1][2]!=-1:\n",
    "                    dp[i][2]=dp[i-1][2]\n",
    "                else:\n",
    "                    dp[i][0]=dp[i-1][0]\n",
    "                    dp[i][1]=dp[i-1][1]\n",
    "                    dp[i][2]=min(dp[i-1][0],dp[i-1][1])+1\n",
    "                    continue\n",
    "            \n",
    "            elif obstacles[i]==1:\n",
    "                if dp[i-1][1]!=-1:\n",
    "                    dp[i][1]=dp[i-1][1]\n",
    "                else:\n",
    "                    dp[i][1]=min(dp[i-1][0]+2,dp[i-1][2]+1)\n",
    "                    dp[i][2]=dp[i-1][2]\n",
    "                    continue\n",
    "                if dp[i-1][2]!=-1:\n",
    "                    dp[i][2]=dp[i-1][2]\n",
    "                else:\n",
    "                    dp[i][2]=min(dp[i-1][0]+2,dp[i-1][1]+1)\n",
    "                    dp[i][1]=dp[i-1][1]\n",
    "                    continue\n",
    "            elif obstacles[i]==2:\n",
    "                if dp[i-1][0]!=-1:\n",
    "                    dp[i][0]=dp[i-1][0]\n",
    "                else:\n",
    "                    dp[i][0]=min(dp[i-1][1]+2,dp[i-1][2]+1)\n",
    "                    dp[i][2]=dp[i-1][2]\n",
    "                    continue\n",
    "                if dp[i-1][2]!=-1:\n",
    "                    dp[i][2]=dp[i-1][2]\n",
    "                else:\n",
    "                    dp[i][2]=min(dp[i-1][1]+2,dp[i-1][0]+1)\n",
    "                    dp[i][0]=dp[i-1][0]\n",
    "                    continue\n",
    "            elif obstacles[i]==3:\n",
    "                if dp[i-1][0]!=-1:\n",
    "                    dp[i][0]=dp[i-1][0]\n",
    "                else:\n",
    "                    dp[i][0]=min(dp[i-1][2]+2,dp[i-1][1]+1)\n",
    "                    dp[i][1]=dp[i-1][1]\n",
    "                    continue\n",
    "                if dp[i-1][1]!=-1:\n",
    "                    dp[i][1]=dp[i-1][1]\n",
    "                else:\n",
    "                    dp[i][1]=min(dp[i-1][2]+2,dp[i-1][0]+1)\n",
    "                    dp[i][0]=dp[i-1][0]\n",
    "                    continue\n",
    "        if(obstacles[n-1]==0):\n",
    "            return min({dp[n-1][0],dp[n-1][1],dp[n-1][2]})\n",
    "        else:\n",
    "            mini=inf\n",
    "            for i in range(3):\n",
    "                if(i+1!=obstacles[n-1] and mini>dp[n-1][i]):\n",
    "                    mini=dp[n-1][i]\n",
    "            return mini                 \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        # 把整个当做二维网格,并将其看做图处理，横着走的权重为0，竖着走的权重为1,。进行dijk算法\n",
    "        n = len(obstacles)\n",
    "        # 表示青蛙到达 i 号点的 j 号跑道时所需要的最少侧跳次数。\n",
    "        dp = [[inf]*3 for _ in range(n)]\n",
    "        # 初始化\n",
    "        dp[0][0] = dp[0][2] = 1\n",
    "        dp[0][1] = 0\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            for j in range(3):\n",
    "                #不换赛道.i-1--->i\n",
    "                if obstacles[i]-1 == j:\n",
    "                    dp[i][j] = inf\n",
    "                else:\n",
    "                    # print(i,j,i-1,j)\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "            #换赛道,从i的其他赛道来，\n",
    "            minCnt = min(dp[i][0],dp[i][1],dp[i][2])\n",
    "            for j in range(3):\n",
    "                if obstacles[i]-1 != j: #当前i节点j赛道没有阻碍才计算最小值。不然直接是INF\n",
    "                    dp[i][j] = min(dp[i][j],minCnt+1)\n",
    "        # print(dp)\n",
    "        return min(dp[-1])\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "\n",
    "        n = len(obstacles)\n",
    "        dis = [[n] * 3 for _ in range(n)]\n",
    "        dis[0][1] = 0\n",
    "        q =deque([(0, 1)]) # 起点\n",
    "        while True:                 # bfs\n",
    "            i, j = q.popleft()\n",
    "            d = dis[i][j]\n",
    "            if i == n - 1: return d #到达终点\n",
    "            if obstacles[i + 1] != j + 1 and d < dis[i + 1][j]: #向右\n",
    "                dis[i + 1][j] = d\n",
    "                q.appendleft((i + 1, j)) #加到队首\n",
    "            for k in (j + 1) % 3, (j + 2) % 3: #枚举到另外两条跑道\n",
    "                if obstacles[i] != k + 1 and d + 1 < dis[i][k]:\n",
    "                    dis[i][k] = d + 1\n",
    "                    q.append((i, k)) # 加到队尾\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        '''\n",
    "        利用图的思想\n",
    "        因为求的是侧跳次数，边权由这个来定义\n",
    "        建图后，就是很简单的最短路dij了\n",
    "\n",
    "        可以用dis代替vis数组\n",
    "        '''\n",
    "        n=len(obstacles)\n",
    "        dis=[[n]*3 for _ in range(n)]\n",
    "        dis[0][1]=0\n",
    "        q=deque([(0,1)])\n",
    "        while True:\n",
    "            i,j=q.popleft()\n",
    "            d=dis[i][j]\n",
    "            if i==n-1:\n",
    "                return d\n",
    "            if obstacles[i+1]!=j+1 and d<dis[i+1][j]: #可以向右\n",
    "                dis[i+1][j]=d\n",
    "                q.appendleft((i+1,j))\n",
    "            for k in (j+1)%3,(j+2)%3:\n",
    "                if obstacles[i]!=k+1 and d+1<dis[i][k]:\n",
    "                    dis[i][k]=d+1\n",
    "                    q.append((i,k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        dis = [[n] * 3 for _ in range(n)]\n",
    "        dis[0][1] = 0\n",
    "        q = deque([(0, 1)])  # 起点\n",
    "        while True:\n",
    "            i, j = q.popleft()\n",
    "            d = dis[i][j]\n",
    "            if i == n - 1: return d  # 到达终点\n",
    "            if obstacles[i + 1] != j + 1 and d < dis[i + 1][j]:  # 向右\n",
    "                dis[i + 1][j] = d\n",
    "                q.appendleft((i + 1, j))  # 加到队首\n",
    "            for k in (j + 1) % 3, (j + 2) % 3:  # 枚举另外两条跑道（向上/向下）\n",
    "                if obstacles[i] != k + 1 and d + 1 < dis[i][k]:\n",
    "                    dis[i][k] = d + 1\n",
    "                    q.append((i, k))  # 加到队尾\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)-1\n",
    "        dp = [[0] * 4 for _ in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for pos in range(1, 4):\n",
    "                res = inf\n",
    "                for j in range(1, 4):\n",
    "                    if pos == j and j!= obstacles[i+1]:\n",
    "                        res = min(res, dp[i+1][pos])\n",
    "                    if j == obstacles[i] or j == obstacles[i+1]:\n",
    "                        continue\n",
    "                    res = min(res, dp[i+1][j]+1)\n",
    "                dp[i][pos] = res\n",
    "        return dp[0][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        dis = [[n] * 3 for _ in range(n)]\n",
    "        dis[0][1] = 0\n",
    "        q = deque([(0, 1)])  # 起点\n",
    "        while True:\n",
    "            i, j = q.popleft()\n",
    "            d = dis[i][j]\n",
    "            if i == n - 1: return d  # 到达终点\n",
    "            if obstacles[i + 1] != j + 1 and d < dis[i + 1][j]:  # 向右\n",
    "                dis[i + 1][j] = d\n",
    "                q.appendleft((i + 1, j))  # 加到队首\n",
    "            for k in (j + 1) % 3, (j + 2) % 3:  # 枚举另外两条跑道（向上/向下）\n",
    "                if obstacles[i] != k + 1 and d + 1 < dis[i][k]:\n",
    "                    dis[i][k] = d + 1\n",
    "                    q.append((i, k))  # 加到队尾\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        dp = [[float('inf')] * 3 for _ in range(n)]\n",
    "        dp[0][0] = dp[0][2] = 1\n",
    "        dp[0][1] = 0\n",
    "        for i in range(1, n):\n",
    "            cur_obstacle = obstacles[i] - 1\n",
    "            for j in range(3):\n",
    "                # cur obstacle => inf\n",
    "                if j == cur_obstacle:\n",
    "                    continue\n",
    "                # from itself\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                # from other\n",
    "                for k in range(3):\n",
    "                    if k == j or k == cur_obstacle:\n",
    "                        continue\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + 1)\n",
    "        return min(dp[n - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles) - 1\n",
    "        dp = [[float('inf')]*3 for _ in range(n+1)]\n",
    "        dp[0][1] = 0\n",
    "        dp[0][0], dp[0][2] = 1,1\n",
    "        for i in range(1,n+1):\n",
    "            ob = obstacles[i] - 1\n",
    "            min_v = float('inf')\n",
    "            for j in range(3):\n",
    "                if not j==ob:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                    min_v = min(min_v, dp[i][j])\n",
    "            for j in range(3):\n",
    "                if (not dp[i][j]<float('inf')) and j!=ob:\n",
    "                    dp[i][j] = min_v + 1\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        length = len(obstacles)\n",
    "        dp = [[float('inf')] * 3 for _ in range(length)]\n",
    "        dp[0][0] = 1\n",
    "        dp[0][1] = 0\n",
    "        dp[0][2] = 1\n",
    "\n",
    "        for i in range(1, length):\n",
    "            minCnt = float('inf')\n",
    "            for j in range(3):\n",
    "                if obstacles[i] == j + 1:\n",
    "                    dp[i][j] = float('inf')\n",
    "                else:\n",
    "                    minCnt = min(minCnt, dp[i-1][j])\n",
    "\n",
    "            for j in range(3):\n",
    "                if obstacles[i] != j + 1:\n",
    "                    dp[i][j] = min(dp[i-1][j], minCnt + 1)\n",
    "\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSideJumps(self, obstacles: List[int]) -> int:\n",
    "        n = len(obstacles)\n",
    "        dp = [[0 for i in range(3)] for j in range(n)]\n",
    "        dp[0][1], dp[0][0], dp[0][2] = 0, 1, 1\n",
    "        for i in range(n - 1):\n",
    "            dp[i + 1][0] = min(dp[i][0], min(dp[i][1], dp[i][2]) + 1)\n",
    "            dp[i + 1][1] = min(dp[i][1], min(dp[i][0], dp[i][2]) + 1)\n",
    "            dp[i + 1][2] = min(dp[i][2], min(dp[i][1], dp[i][0]) + 1)\n",
    "\n",
    "            if obstacles[i + 1] == 1:\n",
    "                dp[i + 1][0] = n + 1\n",
    "                dp[i + 1][1] = min(dp[i][1], dp[i][2] + 1)\n",
    "                dp[i + 1][2] = min(dp[i][2], dp[i][1] + 1)\n",
    "\n",
    "            if obstacles[i + 1] == 2:\n",
    "                dp[i + 1][1] = n + 1\n",
    "                dp[i + 1][0] = min(dp[i][0], dp[i][2] + 1)\n",
    "                dp[i + 1][2] = min(dp[i][2], dp[i][0] + 1)\n",
    "\n",
    "            if obstacles[i + 1] == 3:\n",
    "                dp[i + 1][2] = n + 1\n",
    "                dp[i + 1][0] = min(dp[i][0], dp[i][1] + 1)\n",
    "                dp[i + 1][1] = min(dp[i][1], dp[i][0] + 1)\n",
    "\n",
    "        return min(dp[n - 1])\n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
